#pragma once

#include <compl.h>

/* 通用函数 */
#define list_entry(__type, __item, __field)	\
	container_of(__item, __type, __field)

#define list_is_empty(__list)			\
	((__list)->next == __list)


#define list_first_entry(ptr, type, member)	\
	list_entry((ptr)->next, type, member)

#define list_entry_is_head(pos, head, member)	\
	(&pos->member == (head))

#define list_next_entry(pos, member)		\
	list_entry((pos)->member.next, typeof(*(pos)), member)

#define list_traverse(pos, head, member)		\
	for (typeof(*head##_traversal_type) pos = list_first_entry(head, typeof(*pos), member);\
		!list_entry_is_head(pos, head, member);	\
		pos = list_next_entry(pos, member))

#define list_map_entry(head, member, cfunc)	\
	list_traverse(cfunc##_pos, head, member){ func(cfunc##_pos); }


/* 单链表 */
typedef struct slist {
	struct slist *next;
} slist_t;

#define __SLIST_HEAD_INIT_VAL(name)		\
	{ &(name) }

#define DEF_SLIST_HEAD(name)			\
	struct slist name = __SLIST_HEAD_INIT_VAL(name)

#define slist_traversable(type,name,target_member)	\
	union { slist_t name; type *name##_traversal_type; }

/* 单链表只能插头部 */
SAI void slist_init(slist_t *head){
	head->next = head;
}
SAI void __slist_push_head(slist_t *head, slist_t *node_start, slist_t *node_end){
	/* assert node_start 到 node_end 是合法的 */
	/* node_end->next = node->start */
	node_end->next = head->next;
	head->next = node_start;
}
SAI slist_t *__slist_pop(slist_t *head){
	slist_t *node = head->next;
	head->next = node->next;
	return node;
}
SAI size_t slist_len_noloop(slist_t *head){
	size_t cnt = 0;
	while (head) {
		cnt++;
		head = head->next;
	}
	return cnt;
}

/* push和pop */
SAI void slist_push(slist_t *head, slist_t *node){
	__slist_push_head(head, node, node);
}
SAI void slist_append(slist_t *head, slist_t *start, slist_t *end){
	__slist_push_head(head, start, end);
}
SAI slist_t *slist_pop(slist_t *head){
	slist_t *node = __slist_pop(head);
	return ((node == head) ? (slist_t*)NULL_PTR : node); 
}

/* dlist */
typedef struct dlist {
	struct dlist *next;
	struct dlist *prev;
} dlist_t;

#define dlist_traversable(type, name, target_member) \
	union { dlist_t name; type *name##_traversal_type; }

#define list_last_entry(ptr, type, member) \
	list_entry((ptr)->prev, type, member)


#define __DLIST_HEAD_INIT_VAL(name) \
	{ &(name), &(name) }

#define DEF_DLIST_HEAD(name)		\
	struct dlist name = __DLIST_HEAD_INIT_VAL(name)

/* 双链表 */
SAI void dlist_init(dlist_t *head){
	head->next = head;
	head->prev = head;
}

SAI void __dlist_insert(dlist_t *prev, dlist_t *nhead, dlist_t *ntail, dlist_t *next){
	prev->next = nhead;
	next->prev = ntail;

	nhead->prev = prev;
	ntail->next = next;
}

SAI void __dlist_add_head(dlist_t *head, dlist_t *nhead, dlist_t *ntail){
	dlist_t *first = head->next;

	// ntail->next = first;
	// first->prev = ntail;

	// head->next = nhead;
	// nhead->prev = head;

	__dlist_insert(head, nhead, ntail, first);

}

SAI void __dlist_add_tail(dlist_t *head, dlist_t *nhead, dlist_t *ntail){
	dlist_t *tail = head->prev;

	// tail->next = nhead;
	// nhead->prev = tail;
	
	// ntail->next = head;
	// head->prev = ntail;

	__dlist_insert(tail, nhead, ntail, head);
}
SAI void dlist_del(dlist_t *prev, dlist_t *next){
	prev->next = next;
	next->prev = prev;
}
SAI void __dlist_del(dlist_t *head){
	dlist_t *prev = head->prev;
	dlist_t *next = head->next;

	prev->next = next;
	next->prev = prev;
}

SAI void __dlist_replace(dlist_t *from, dlist_t *to){
	dlist_t *prev = from->prev;
	dlist_t *next = from->next;

	prev->next = to;
	next->prev = to;
	to->next = next;
	to->prev = prev; 
}

SAI void dlist_add_head(dlist_t *head, dlist_t *node){
	__dlist_add_head(head, node, node);
}

SAI void dlist_add_tail(dlist_t *head, dlist_t *node){
	__dlist_add_tail(head, node, node);
}
